package leetcode.editor.cn;

import java.util.*;

/**
 * @id: 51
 * @title: N 皇后
 */
 
//n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 
//
// 
// 
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 4
//输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[["Q"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 
// 
// 
// Related Topics 数组 回溯 
// 👍 1140 👎 0

public class P51NQueens {
    public static void main(String[] args) {
        Solution solution = new P51NQueens().new Solution();
        // todo
        System.out.println(solution.solveNQueens(4));

    }
    
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
//    public List<List<String>> solveNQueens(int n) {
//        List<List<String>> ans = new ArrayList<>();
//        for (int start=0; start < n; ++start) {
//            // 标志每一个列是否被使用
//            int[] queens = new int[n];
//            Arrays.fill(queens, -1);
//            Set<Integer> pies = new HashSet<>();
//            Set<Integer> nas = new HashSet<>();
//            for (int level = 0; level < n; ++level) {
//                if (level == 0) {
//                    queens[level] = start;
//                    pies.add(level + start);
//                    nas.add(level - start);
//                    continue;
//                }
//                for (int clu = 0; clu < n; ++clu) {
//                    if (queens[clu] != -1
//                            || pies.contains(level + clu)
//                            || nas.contains(level - clu)) {
//                        continue;
//                    }
//                    queens[level] = clu;
//                    pies.add(level + clu);
//                    nas.add(level - clu);
//                    break;
//                }
//            }
//
//            genBoard(ans, queens);
//        }
//        return ans;
//    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        if (n <= 0) {
            return ans;
        }
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        Set<Integer> clus = new HashSet<>();
        Set<Integer> pies = new HashSet<>();
        Set<Integer> nas = new HashSet<>();
        backtrack(ans, n, 0, queens, clus, pies, nas);
        return ans;
    }

    private void backtrack(List<List<String>> ans,
                           int n,
                           int level,
                           int[] queens,
                           Set<Integer> clus,
                           Set<Integer> pies,
                           Set<Integer> nas) {
        if (level == n) {
            return;
        }
        for (int clu = 0; clu < n; ++clu) {
            if (clus.contains(clu)
                    || pies.contains(level + clu)
                    || nas.contains(level - clu)) {
                continue;
            }
            queens[level] = clu;
            clus.add(clu);
            pies.add(level + clu);
            nas.add(level - clu);
            backtrack(ans, n, level + 1, queens, clus, pies, nas);
            genBoard(ans, queens);
            // 每次回溯到上一层，也就是说下面一层的所有结果都要清空，才能回到上一层然后重试上一层的其他列
            clus.remove(clu);
            pies.remove(level + clu);
            nas.remove(level - clu);
            queens[level] = -1;
        }
    }

    private void genBoard(List<List<String>> ans, int[] queens) {
        List<String> board = new ArrayList<>(queens.length);
        for (int i : queens) {
            if (i == -1) {
                return;
            }
            char[] row = new char[queens.length];
            Arrays.fill(row, '.');
            row[i] = 'Q';
            board.add(new String(row));
        }
        ans.add(board);
    }


}
//leetcode submit region end(Prohibit modification and deletion)


}